README.md

105. Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:

You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7] inorder = [9,3,15,20,7] 

Return the following binary tree:

 3 / \ 9 20 / \ 15 7 

Solutions (Python)

1. Recursion

# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution: defbuildTree(self, preorder: List[int], inorder: List[int]) ->TreeNode: ifnotpreorder: returnNoneroot=TreeNode(preorder[0]) i=inorder.index(root.val) root.left=self.buildTree(preorder[1:i+1], inorder[:i]) root.right=self.buildTree(preorder[i+1:], inorder[i+1:]) returnroot